<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>Maxmilite</title>
    <link rel="icon" href="../icon.png" type="image/x-icon">
</head>

<link rel="stylesheet" href="../css/style-archive.css">

<canvas id="snow-flake-app"></canvas>
<script src="../js/snow-flake-app.js"></script>

<!-- <ul class="nav">
    <li style="width: 40%;">
        <div>
            <p style="font-size: xx-large;"><img src="../icon.png" height="40px" width="40px"
                    style="border-radius: 4px;">&nbsp;Maxmilite</p>
        </div>
    </li>
</ul> -->

<div class="main">
    <h1 style="text-align: center;">
        题解 AT4285 【[ABC116D] Various Sushi】
    </h1>
</div>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<xmp theme="united" style="display:none;" id="section">
### Explanation

有 $N$ 个寿司，选 $K$ 个使得满足最大值。

### Solution

#### Solution 1

$N$ 个选 $K$ 个，乍一看就觉得是背包 DP。

按照背包 DP 解法，

用 $f[i]$ 表示在这 $N$ 个寿司选 $i$ 个寿司所产生的最大满足。

一开始先对所有寿司按照类型排个序，以便于算种类数。

然后按照每个物品的重量为 $1$ 直接往上套 01DP 模板、特判一下寿司种类即可。

由于会爆 $int$，记得开 $long \ long$

```cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k, f[100005], val[100005];
struct node
{
    long long t, d;
    bool operator<(const node &x) const
    {
        if (t == x.t)
            return d > x.d;
        return t < x.t;
    }
} a[100005];
int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i(1); i <= n; ++i)
        scanf("%lld%lld", &a[i].t, &a[i].d);
    sort(a + 1, a + n + 1);
    for (int i(1); i <= n; ++i)
    {
        if (a[i].t != a[i - 1].t) //特判寿司种类
            for (int j(k); j; --j)
            {
                if (f[j - 1] + a[i].d + (val[j - 1] + 1) * (val[j - 1] + 1) - (val[j - 1] * val[j - 1]) > f[j]) //dp
                    f[j] = f[j - 1] + a[i].d + (val[j - 1] + 1) * (val[j - 1] + 1) - (val[j - 1] * val[j - 1]), val[j] = val[j - 1] + 1;
            }
        else
            for (int j(k); j; --j)
            {
                if (f[j - 1] + a[i].d > f[j]) //dp
                    f[j] = f[j - 1] + a[i].d, val[j] = val[j - 1];
            }
    }

    printf("%lld\n", f[k]);
    return 0;
}
```

然后因为 $N \leq 10 ^ 5$，所以我们的 $O(n ^ 2)$ 成功地 T 飞了 /kk

#### Solution 2

考虑一下我们的 DP 哪里最耗时间。

对于某些寿司，加到已经有的寿司队列里不会对寿司种类数产生影响，并且他的价值比队列里的所有寿司都低。

所以对于这种寿司，我们要坚决阻止。

所以我们**小小贪心一下，先挑出来 $k$ 个价值最高的寿司，然后去判寿司种类对结果产生的影响**

好的我们开始。

1. 找出来前 $k$ 个价值最高的寿司

这里我们可以用一个优先队列来找出这些寿司。

在部分代码环节，我们不妨用 $tmp$ 来表示寿司。

用 $q$ 大根堆存储所有寿司，用 $rev$ 小根堆存储 $k$ 个寿司，以备后用

伪代码如下

```
struct Sushi
{
  long long t,d;
  bool operator<(const node &x) const
    return d < x.d;
} tmp;

priority_queue<Sushi> q;

priority_queue<Sushi, vector<Sushi>, greater<Sushi> > rev;

while (input tmp)
  q.push(tmp)

for i from 1 to k
  rev.push(q.top())
  q.pop()
```

2. 在存 $k$ 个寿司的同时，记录一下目前寿司的种类和总满足

由于 $1 \leq t_i \leq N$ 所以这里我用一个 $num$ 数组来记录每中寿司 $t$ 的数量，用一个 $cnt$ 记录总的寿司种类数，用 $sum$ 记录一下总满足

伪代码如下

```
while rev.push(q.top())

    if num[q.top().t] == 0
        cnt++

    num[q.top().t]++
    sum += q.top().d

```

3. 计算一下当前的总满足

这里我用一个 $ans$ 记录

伪代码如下

```
ans = sum + cnt * cnt
```

4. 开始判断寿司种类

首先什么样的寿司对我们的答案可能有贡献呢？

##### 这个寿司带来的 “多样性加成” 的收益大于 “基础美味程度总和” 的损失。

所以我们的目标就很明确了。

对于带不来 “多样性加成” 的寿司，我们直接扔掉。

对于带的来 “多样性加成” 的寿司，我们去找到现有的 $k$ 个寿司中 **去掉不会对现有种类造成影响且价值最小的** 寿司，将两寿司交换。

伪代码如下

```
while q.size() && rev.size()
    if num[q.top().t] != 0 // 寿司没有带来 “多样性加成”，不能要，去掉
        q.pop()
        continue
    if num[rev.top().t] == 1 // 去掉该寿司会对现有种类造成影响，不能去，找当前的下一个寿司
        rev.pop()
        continue
// 这样可以找到符合要求的两个寿司交换
```

找到了以后，我们进行交换，计算交换后是否满足

>_这个寿司带来的 “多样性加成” 的收益大于 “基础美味程度总和” 的损失。_

且计算新的总满足，和原来的比较。

伪代码如下

```
    num[rev.top().t] --
    num[q.top().t] ++
    cnt ++
    sum -= rev.top().d
    sum += q.top().d
    ans = max (ans, sum + cnt * cnt)
```

最终找到最大的总满足，得到正解。

### AC Code

```cpp
#include <bits/stdc++.h>
using namespace std;
long long n, k, ans, cnt, num[100005], sum;

struct node
{
    long long t, d;
    bool operator<(const node &x) const
    { return d < x.d; }
    bool operator>(const node &x) const
    { return d > x.d; }
} tmp;

priority_queue<node> q;
priority_queue<node, vector<node>, greater<node>> rev;

int main()
{
    scanf("%lld%lld", &n, &k);
    for (int i(1); i <= n; ++i)
    {
        scanf("%lld%lld", &tmp.t, &tmp.d);
        q.push(tmp);
    }
    for (int i(1); i <= k; ++i)
    {
        if (num[q.top().t]++ == 0)
            cnt++;
        sum += q.top().d;
        rev.push(q.top());
        q.pop();
    }
    ans = sum + cnt * cnt;
    while (q.size() && rev.size())
    {
        if (num[q.top().t] != 0)
        {
            q.pop();
            continue;
        }
        if (num[rev.top().t] == 1)
        {
            rev.pop();
            continue;
        }
        num[rev.top().t]--;
        num[q.top().t]++;
        cnt++;
        sum -= rev.top().d;
        sum += q.top().d;
        rev.pop();
        q.pop();
        ans = sum + cnt * cnt > ans ? sum + cnt * cnt : ans;
    }
    printf("%lld\n", ans);
    return 0;
}
```
</xmp>


<script src="strapdown/v/0.2/strapdown.js"></script>

<div>
    <!-- Button Here -->
    <!-- Fixed Button 2021-04-18-->
    <a class="button" href="../archives.html" style="width: 40%; border-radius: 8px; margin-left: 30%; margin-top: 100px;  margin-bottom: 40px">
        <p style="font-size: 2vmax;">
            <<< Return to archive list </p>
    </a>
</div>

</html>